package com.example.leetcode.trainingcamp.week4.Sunday;

/**
 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 *
 * <p>示例：
 *
 * <p>输入： arr = [1,3,5,7,2,4,6,8], k = 4 输出： [1,2,3,4]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/smallest-k-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer17_14 {

    public int[] smallestK(int[] arr, int k) {
        quickSort(arr,0,arr.length-1);
        int[] result = new int[k];
        if (k >= 0) System.arraycopy(arr, 0, result, 0, k);
        return result;
    }


    public void quickSort(int[] arr ,int low,int high){
        if (low>high){
            return;
        }
        int i = low,j= high;
        int temp = arr[low];
        while (i<j){
            while (i<j && arr[j] >= temp) j--;
            while (i<j && arr[i] <= temp) i++;
            if (i<j){
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
        }
        arr[low] = arr[i];
        arr[i] = temp;
        quickSort(arr,low,i-1);
        quickSort(arr,i+1,high);
    }
}


class DemoOffer17_14{
  public static void main(String[] args) {
    Offer17_14 o = new Offer17_14();
    int[] arr = {1,3,5,7,2,4,6,8};
    int k= 4;
    int[] ints = o.smallestK(arr, k);
    for (int i : ints) {
      System.out.println(i+" ");
    }
  }
}